//
// Created by 下次一定 on 2021/9/21.
//
/*
 * 计算第一个点到最后一个点的距离
 * 单源最短路:朴素Dijkstra
 * 边数很多 可以用邻接矩阵存储
 * */


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10;
int map[N][N];
int n, m;
int dist[N];
bool st[N];


int dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;

    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = true;

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j],dist[t]+map[t][j]);

    }
    if(dist[n] == 0x3f) return -1;
    return dist[n];
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            map[i][j] = 100010;
        }
    }
    // 一键赋值
    memset(map, 0x3f, sizeof(map));

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a;
        cin >> b;
        cin >> w;
        map[a][b] = min(map[a][b], w);
    }

    int t = dijkstra();

    cout << t << endl;
}

